package my.suveng.struct.trie;

import my.suveng.util.json.Jackson;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符字典树
 * @author suwenguang
 **/
public class Trie implements ITrie<String> {

    /**
     * 根节点
     */
    private final ITrieNode root = new TrieNode();

    /**
     * 构造函数, 以一系列的字典作为入参,插入到字典树中
     * @author suwenguang
     */
    public Trie(ArrayList<String> keys) {
        for (String key : keys) {
            if (!insert(key)) {
                throw new RuntimeException("构造字典树失败");
            }
        }
    }

    public Trie() {

    }

    /**
     * 搜索字典
     * @author suwenguang
     */
    @Override
    public ITrieNode get(String key) {
        ITrieNode node = startWith(key);
        if (node != null) {
            boolean end = node.isEnd();
            if (end) {
                return node;
            }
        }
        return null;
    }

    /**
     * 插入字典
     * 我们通过搜索 Trie 树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况：
     *  链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
     *  链接不存在。创建一个新的节点，并将它与父节点的链接相连，该链接与当前的键字符相匹配。
     * 重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。
     * @author suwenguang
     */
    @Override
    public synchronized boolean insert(String key) {
        // key 不允许空,value不允许空
        if (key == null || "".equals(key)) {
            return false;
        }

        ITrieNode curr = root;
        char[] keys = key.toCharArray();
        for (int i = 0; i < keys.length; i++) {
            // 查询链接是否存在
            ITrieNode e = curr.hasLink(keys[i]);
            if (e != null) {
                // 存在,继续移动到下一层
                curr = e;
            } else {
                // 不存在, 新建节点, 并将它与父节点的链接相连，该链接与当前的键字符相匹配
                ITrieNode newNode = curr.insertLink(keys[i]);
                if (newNode == null) {
                    // 创建失败,抛出异常
                    return false;
                }
                curr = newNode;
            }
        }

        //重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。
        curr.setEnd(true);
        return true;
    }

    /**
     *  删除字典
     *  删除 将节点置为false,并检查是否有冗余节点
     */
    @Override
    public synchronized void delete(String key) {
        ITrieNode node = get(key);
        if (node != null) {
            node.setEnd(false);
        }
    }

    /**
     * 清除冗余节点
     */
    @Override
    public synchronized void removeRedundantNode() {
        // 深度遍历
        removeRedundantNode(root);
        System.gc();
    }

    private void removeRedundantNode(ITrieNode node) {
        List<ITrieNode> links = node.getLinks();
        if (links == null || links.size() < 1) {
            return;
        }

        links.removeIf(link -> !existKey(link));
        for (ITrieNode link : links) {
            removeRedundantNode(link);
        }
    }

    /**
     * 节点总数
     */
    @Override
    public int countNode() {
        return countNode(root);
    }

    private int countNode(ITrieNode node) {
        List<ITrieNode> links = node.getLinks();
        if (links == null || links.size() < 1) {
            return 0;
        }

        int result = links.size();
        for (ITrieNode link : links) {
            int i = countNode(link);
            result += i;
        }
        return result;
    }

    /**
     * 是否存在某个字典
     * @author suwenguang
     */
    @Override
    public boolean exist(String key) {
        return get(key) != null;
    }

    /**
     * 是否存在以某个前缀开始的字典
     */
    @Override
    public boolean existStartWith(String key) {
        // 拿到对应节点
        ITrieNode node = startWith(key);
        // 遍历节点
        return existKey(node);
    }

    /**
     * 判断某个节点是否下面是否有字典
     * @author suwenguang
     */
    @Override
    public boolean existKey(ITrieNode node) {
        if (node == null) {
            return false;
        }

        if (node.isEnd()) {
            return true;
        }

        List<ITrieNode> links = node.getLinks();
        for (ITrieNode link : links) {
            if (existKey(link)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 是否以某个前缀开始的节点列表, 属于中间节点
     *
     * 每个键在 trie 中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始。
     * 检查当前节点中与键字符对应的链接。有两种情况：
     *     存在链接。我们移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
     *     不存在链接。若已无键字符，且当前结点标记为 isEnd，则返回 true。否则有两种可能，均返回 false :
     *         但无法跟随 Trie 树的键路径，找不到键。
     *         但当前结点没有标记为 isEnd。也就是说，待查找键只是Trie树中另一个键的前缀。
     */
    @Override
    public ITrieNode startWith(String key) {
        // key不允许为空
        if (key == null || "".equals(key)) {
            return null;
        }

        ITrieNode curr = root;
        char[] keys = key.toCharArray();
        for (int i = 0; i < keys.length; i++) {
            // 查询链接是否存在
            ITrieNode node = curr.hasLink(keys[i]);
            if (node != null) {
                // 存在, 继续向下寻找
                curr = node;
            } else {
                // 不存在
                return null;
            }
        }

        return curr;
    }

    /**
     * 返回以某个前缀开始的字典
     */
    @Override
    public List<String> trieStartWith(String key) {
        ITrieNode node = startWith(key);
        ArrayList<String> result = new ArrayList<>();
        traverse(key, node, result);
        return result;
    }

    /**
     * 全部字典
     */
    @Override
    public List<String> allToString() {
        ArrayList<String> result = new ArrayList<>();
        List<ITrieNode> links = root.getLinks();
        if (null != links && links.size() > 0) {
            for (ITrieNode link : links) {
                traverse("", link, result);
            }
        }
        return result;
    }

    @Override
    public String toString() {
        ArrayList<String> result = new ArrayList<>();
        List<ITrieNode> links = root.getLinks();
        if (null != links && links.size() > 0) {
            for (ITrieNode link : links) {
                traverse("", link, result);
            }
        }
        return Jackson.toJsonString(result);
    }

    /**
     * 遍历前缀树/字典树, 把字典输出为数组
     * @author suwenguang
     */
    private void traverse(String prefix, ITrieNode node, List<String> result) {
        List<ITrieNode> links = node.getLinks();
        if (node.isEnd()) {
            result.add(prefix + node.getValue());
        }
        for (ITrieNode link : links) {
            traverse(prefix + node.getValue(), link, result);
        }
    }

    /**
     * 默认字典树节点
     * @author suwenguang
     **/
    static class TrieNode implements ITrieNode {

        private final List<ITrieNode> links = new ArrayList<>();
        private final List<Character> linksValue = new ArrayList<>();

        private char value;

        private boolean end;

        @Override
        public List<ITrieNode> getLinks() {
            return links;
        }

        @Override
        public char getValue() {
            return value;
        }

        @Override
        public ITrieNode hasLink(char key) {
            for (ITrieNode node : links) {
                char value = node.getValue();
                if (value == key) {
                    return node;
                }
            }
            return null;
        }

        @Override
        public synchronized ITrieNode insertLink(char key) {
            TrieNode node = new TrieNode();
            node.setValue(key);
            // links.value 去重
            if (!linksValue.contains(key)) {
                linksValue.add(key);
                links.add(node);
            }
            return node;
        }

        @Override
        public void setEnd(boolean end) {
            this.end = end;
        }

        @Override
        public void setValue(char value) {
            this.value = value;
        }

        @Override
        public boolean isEnd() {
            return end;
        }
    }
}


